1. Field of the Invention
The present invention relates to a CRC arithmetic unit for detecting a data transmission error by a CRC (cyclic redundancy check) system employed for transmitting a data string.
2. Description of the Background Art
In relation to communication of a data string, there is a method of determining whether or not the transmitted data string is normal by adding a check bit for an error detection check to an information bit to be transmitted and performing a prescribed operation in receiving. A method employing a parity bit is well known as a simple error detection system. In this method, a single parity bit is added in response to whether the number of xe2x80x9c1xe2x80x9d included in each transmitted data string is even or odd.
A cyclic redundancy check (hereinafter abbreviated as CRC) is a method enhanced in detectability. In the CRC, an operation with a generating polynomial is performed on an information bit to be transmitted.
A method of forming a CRC sign is briefly described. First, it is assumed that P(X) represents an information data string to be transmitted corresponding to an information bit, G(X) represents a generating polynomial, F(X) represents a transmitted data string and R(X) represents a remainder polynomial corresponding to a check bit. These are expressed in sign polynomials. In a sign polynomial, a binary number is expressed in a polynomial. For example, P(X)=xe2x80x9c100 1011 0100 1011xe2x80x9d is expressed as follows:
P(X)=X14+X11+X9+X8+X6+X3+X1+1
When the generating polynomial G(X) is equal to X8+X7+X6+X4+X2+1, the transmitted data string F(X) is obtained by the following expressions (1) to (3):
First, the information data string P(X) is multiplied by the high-order term X8 of the generating polynomial G(X) for obtaining Pxe2x80x2(X) as follows:
Pxe2x80x2(X)=P(X)xc3x97X8xe2x80x83xe2x80x83(1)
Then, Pxe2x80x2(X) is subjected to mod2 division described later by the generating polynomial G(X) for obtaining the remainder polynomial R(X). It is assumed that xe2x80x9c/xe2x80x9d denotes the mod2 division described later.
R(X)=Pxe2x80x2(X)/G(X)xe2x80x83xe2x80x83(2)
The obtained remainder polynomial R(X) is added to Pxe2x80x2(X) for obtaining the transmitted data string F(X) as follows:
F(X)=Pxe2x80x2(X)+R(X)xe2x80x83xe2x80x83(3)
FIG. 15 is a diagram for illustrating the mod2 division for obtaining the check bit from the information bit and the generating polynomial.
The operation of obtaining the check bit from the information bit when the generating polynomial G(X) is equal to X8+X7+X6+X4+X2+1 is described with reference to FIG. 15. xe2x80x9c1 1101 0101xe2x80x9d corresponds to the generating polynomial, and the information bit is xe2x80x9c100 1011 0100 1011xe2x80x9d.
The number 0 of a bit numberxe2x88x921 in the generating polynomial is first added to the low order of the information bit. This processing corresponds to the operation shown in the expression (2).
The mod2 operation is performed on each bit of the generating polynomial in descending order. However, the mod2 operation generates no carry or negative carry dissimilarly to general division. In other words, the exclusive OR of each information bit and each bit of the generating polynominal is sequentially calculated. The most significant result is necessarily xe2x80x9c0xe2x80x9d and hence at least a single information bit is supplied to the lower result to match with the bit number of the generating polynomial. Referring to FIG. 15, symbol A denotes an intermediate result obtained in this stage.
The mod2 operation is thereafter similarly repeated, and terminated when the result is finally less than the bit number of the generating polynomial. The finally obtained remainder xe2x80x9c00110001xe2x80x9d is the obtained check bit. The operation of repeating the mod2 operation for obtaining the remainder is referred to as mod2 division in this specification.
The check bit obtained in the aforementioned manner is transmitted subsequently to the information bit when transmitting the data string. The receiving end confirms whether or not a transmission error occurs on the basis of the transmitted information and check bits.
FIG. 16 is a diagram for illustrating the operation for confirming whether or not a transmission error occurs.
Referring to FIG. 16, the mod2 division is performed on the data string transmitted with the check bit xe2x80x9c0011 0001xe2x80x9d added to the lower side of the information bit xe2x80x9c100 1011 0100 1011xe2x80x9d by the generating polynomial xe2x80x9c1 1101 0101xe2x80x9d. As to the mod2 division described with reference to FIG. 15, redundant description is not repeated.
When transmission is correctly performed, the remainder is zero and it is confirmable that no transmission error occurs.
FIG. 17 is a conceptual diagram showing the structure of a conventional CRC arithmetic unit 100 performing the division illustrated in FIGS. 15 and 16.
Referring to FIG. 17, the CRC arithmetic unit 100 includes XOR circuits 102 to 110 operating and outputting exclusive OR and registers 112 to 126 driven by a clock signal (not shown) for capturing and holding data.
The XOR circuit 102 operates and outputs the exclusive OR of a data string input in the CRC arithmetic unit 100 and a value held in the register 126. The register 112 receives the output of the XOR circuit 102 and holds the same for a single clock period. The register 114 receives an output of the register 112 and holds the same for a single clock period. The XOR circuit 104 operates and outputs the exclusive OR of outputs of the registers 114 and 126. The register 116 receives the output of the XOR circuit 104 and holds the same for a single clock period. The register 118 receives an output of the register 116 and holds the same for a single clock period.
The XOR circuit 106 operates and outputs the exclusive OR of the outputs from the registers 118 and 126. The register 120 receives the output of the XOR circuit 106 and holds the same for a single clock period. The register 122 receives an output of the register 120 and holds the same for a single clock period. The XOR circuit 108 operates and outputs the exclusive OR of outputs from the registers 122 and 126. The register 124 receives the output of the XOR circuit 108 and holds the same for a single clock period. The XOR circuit 110 outputs the exclusive OR of outputs from the registers 124 and 126. The register 126 receives the output of the XOR circuit 110 and holds the same for a single clock period.
FIGS. 18 to 25 illustrate the process of operations in the CRC arithmetic unit 100 shown in FIG. 17. The process up to the intermediate stage of the mod2 division shown in FIG. 15 is described with reference to FIGS. 18 to 25.
Referring to FIGS. 15 and 18, the CRC arithmetic unit 100 is provided with the XOR circuits 102 to 110 in correspondence to positions where the bits of xe2x80x9c1xe2x80x9d of the generating polynomial are present. In other words, the structure of the CRC arithmetic unit 100 corresponds to the generating polynomial xe2x80x9c1 1101 0101xe2x80x9d.
First, it is assumed that all registers 112 to 126 initially hold xe2x80x9c0xe2x80x9d. Although not illustrated, it is general that values held in all registers 112 to 126 are initialized to xe2x80x9c0xe2x80x9d in response to a reset signal. While the register 126 holds xe2x80x9c0xe2x80x9d, the XOR circuits 102 to 110 output data received from preceding stages to subsequent stages intact. In other words, the CRC arithmetic unit 100 acts as a simple shift register until data xe2x80x9c1xe2x80x9d arrives at the register 126.
After a lapse of a prescribed time, the registers 112 to 126 hold xe2x80x9c1001 0110xe2x80x9d. xe2x80x9c1xe2x80x9d is input in an input of the CRC arithmetic unit 100.
Referring to FIG. 19, the registers 112 to 126 hold results operated in the XOR circuits 102 to 110 after a lapse of a single clock period. The next bit xe2x80x9c0xe2x80x9d is input in the input of the CRC arithmetic unit 100. This state corresponds to the intermediate result A shown in FIG. 15.
FIG. 20 shows the state in a next clock cycle. At this time, the registers 112 to 126 hold xe2x80x9c0010 0101xe2x80x9d.
FIG. 21 shows the state in a next clock cycle. At this time, the register 126 holds xe2x80x9c0xe2x80x9d and hence the values are shifted to the upper side one bit position. Thus, the registers 122 to 126 hold xe2x80x9c0100 1010xe2x80x9d.
FIG. 22 shows the state in a next clock cycle. The register 126 holds xe2x80x9c0xe2x80x9d in FIG. 21, and hence the CRC arithmetic unit 100 holds xe2x80x9c1001 0101xe2x80x9d shifted to the upper side one bit position. xe2x80x9c0xe2x80x9d is newly input in the input of the CRC arithmetic unit 100. This state corresponds to an intermediate result B shown in FIG. 15.
In a next clock cycle, the registers 112 to 126 hold xe2x80x9c1111 1111xe2x80x9d as shown in FIG. 23. xe2x80x9c1xe2x80x9d is newly input in the input of the CRC arithmetic unit 100. This state corresponds to an intermediate result C shown in FIG. 15. In a next clock cycle, the registers 112 to 126 hold xe2x80x9c0010 1010xe2x80x9d as shown in FIG. 24.
In a next clock cycle, the registers 112 to 126 hold xe2x80x9c0101 0101xe2x80x9d as shown in FIG. 25. In a next clock cycle, the registers 112 to 126 hold an intermediate result D shown in FIG. 15.
A plurality of systems employing different generating polynomials are present for the CRC operation. In the conventional CRC arithmetic unit 100 described above, the positions for inserting the XOR circuits 102 to 110 must be changed for changing the used generating polynomial, while it is difficult to change the positions when the generating polynomial is once decided.
Further, the conventional arithmetic unit 100 can handle only a 1-bit input in a single clock cycle, to disadvantageously result in a long operation time.
An object of the present invention is to provide a CRC arithmetic unit capable of readily dealing with change of a generating polynomial and performing an operation at a high speed.
Briefly stated, the present invention is directed to a CRC arithmetic unit for performing error detection in a cyclic redundancy check system on object data on the basis of a generating polynomial, which comprises a main arithmetic circuit and a hold circuit.
The main arithmetic circuit sequentially receives a plurality of split data obtained by splitting signal bits included in the object data into a plurality of bits for performing arithmetic processing according to the generating polynomial. The main arithmetic circuit performs the arithmetic processing on first data included in the plurality of split data and second data obtained by performing the arithmetic processing on part of the object data received before receiving the first data and generating third data.
The hold circuit holds the second data and supplies the same to the main arithmetic circuit while holding the third data.
Accordingly, a principal advantage of the present invention resides in that the CRC arithmetic unit simultaneously batch-processing a plurality of bits in a clock cycle can perform a CRC operation at a high speed.